package com.backpack;

/**
 * 最大子数组和
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 */
public class MaximumSubarray0118_53 {
    public int maxSubArray(int[] nums) {
        if(nums.length == 1) return nums[0];
        //动态规划
        //dp 含义：dp[i]表示包括下标i（以nums[i]为结尾）的  最大连续子序列和为dp[i]。
        int[] dp = new int[nums.length];
        //返回值：dp中的最大值
        int res = nums[0];

        //初始化
        dp[0] = nums[0];

//         for (int i = 1; i < nums.length; i++) {
//             if(dp[i-1] + nums[i] < 0){
//                 dp[i] = nums[i];
//             }else {
//                 dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
//             }
//             if(dp[i] >= res) res = dp[i];
//         }
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            if(dp[i] >= res) res = dp[i];
        }
        return res;
    }
}
